/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    // 比较函数
    struct cmp
    {
        bool operator()(const ListNode* l1, const ListNode* l2)
        {
            return l1->val > l2->val;
        }
    };

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // 创建一个小根堆
        priority_queue<ListNode*, vector<ListNode*>, cmp> heap;

        // 让所有的头结点进入小根堆
        for(auto& l : lists)
            if(l) heap.push(l);

        // 合并 k 个有序链表
        ListNode* ret = new ListNode(0);
        ListNode* prev = ret;
        while(!heap.empty())
        {
            ListNode* t = heap.top();
            heap.pop();
            prev->next = t;
            prev = t;
            if(t->next)
                heap.push(t->next);
        }

        prev = ret->next;
        delete ret;

        return prev;
    }
};

//###################################################################
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size() - 1);
    }

    ListNode* merge(vector<ListNode*>& lists, int left, int right)
    {
        if(left > right)
            return nullptr;
        if(left == right)
            return lists[left];

        // 1. 平分数组
        int mid = (left + right) >> 1;
        // [left, mid] [mid + 1, right]

        // 2. 递归处理左右区间
        ListNode* l1 = merge(lists, left, mid);
        ListNode* l2 = merge(lists, mid + 1, right);

        // 3. 合并两个有序链表
        return mergeToList(l1, l2);
    }

    ListNode* mergeToList(ListNode* l1, ListNode* l2)
    {
        if(l1 == nullptr)
            return l2;
        if(l2 == nullptr)
            return l1;

        // 合并两个有序链表
        ListNode head;
        ListNode* cur1 = l1, *cur2 = l2, *prev = &head;
        head.next = nullptr;

        while(cur1 && cur2)
        {
            if(cur1->val <= cur2->val)
            {
                prev = prev->next = cur1;
                cur1 = cur1->next;
            }
            else
            {
                prev = prev->next = cur2;
                cur2 = cur2->next;
            }
        }

        if(cur1)
            prev->next = cur1;
        if(cur2)
            prev->next = cur2;

        return head.next;
    }
};